package leetcode.day_2020_2021_1_18_2021_1_24;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 * 3. 无重复字符的最长子串
 */
public class Leetcode0003 {

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb"));
        System.out.println(lengthOfLongestSubstring("bbbbb"));
        System.out.println(lengthOfLongestSubstring("pwwkew"));
    }

    public static int lengthOfLongestSubstring(String s) {
        if (s == null) {
            return 0;
        }
        int left = 0, right = 0;
        Map<Character, Integer> window = new HashMap<>();
        int maxLength = 0;
        while (right < s.length()) {
            char c1 = s.charAt(right);
            window.put(c1, window.getOrDefault(c1, 0) + 1);
            right++;

            while (window.get(c1) > 1) {
                char c2 = s.charAt(left);
                if(window.get(c2) > 1) {
                    window.put(c2, window.get(c2)-1);
                } else {
                    window.remove(c2);
                }
                left++;
            }

            if (right-left > maxLength) {
                maxLength = right - left;
            }
        }
        return maxLength;
    }
}
